package com.clstu.avl;

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import sun.security.mscapi.CPublicKey;

import java.util.HashSet;
import java.util.Set;

/**
 * 研究平衡二叉树(有序的)
 * 二叉排序树在大多数情况不好的时候会退化成将近链表的结构,会降低查询效率
 * 为了提高它的查询效率,于是有了平衡二叉树
 */
public class AVLTreeDemo {
    public static void main(String[] args) {
        //测试
        AVLTree avlTree = new AVLTree();
//        int[] arr = {1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1};
//        int[] arr = {10,11,7,6,8,9};//这个序列添加之后如果只有单选择,仍不能保证平衡
//        int[] arr = new int[10];
//        for (int i = 0; i <arr.length; i++) {
//            arr[i] = (int) (Math.random()*10);
//        }
//        for (int i = 0; i < arr.length; i++) {
//            avlTree.add(new Node(arr[i]));
//        }
//        System.out.println("root"+avlTree.getRoot());
//        System.out.println("左高度:"+avlTree.getRoot().leftHeight());
//        System.out.println("右高度:"+avlTree.getRoot().rightHeight());
//        avlTree.infixOrder();
        int[] arr = {2,1,3};
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }
        System.out.println(isValidBST(avlTree.getRoot()));
    }
    public static Node pre=null;
    //编写方法判断这棵树是不是二叉排序树
    public static boolean isValidBST(Node root) {
        //思路分析:
        //如果是搜索二叉树,在中序遍历的时候一定是升序的
        //于是,采用中序遍历的方式
        //可以用一个全局变量来记录前一个节点,如果大于当前节点,则返回false
        //中序遍历 左边 ---> 自己 ---> 右边
        //先判断是否不用判断
        if(root == null){
            return true;
        }
        //左递归
        if(root.left!=null && !isValidBST(root.left)){
            return false;
        }
        //自己
        if(pre != null){
            if(pre.value>root.value){
                return false;
            }
        }
        //右递归
        if(root.right!=null && !isValidBST(root.left)){
            return false;
        }
        //pre的值后移
        pre = root;
        //如果没有失败,说明是搜索二叉树
        return true;
    }
}
/**
 * 平衡二叉树类
 */
class AVLTree{
    private Node root;
    //构造器
    public AVLTree(Node root){
        this.root = root;
    }

    //无参构造器
    public AVLTree(){}

    //编写方法添加节点
    public void add(Node node){
        //先判断是否树空
        if(root == null){
            root = node;
            return;
        }
        //添加
        root.add(node);
    }

    //不足之处:当二叉树种有两个节点值相同时删不掉(通过方法重载,指定节点删除的方式解决掉了这个问题!!)
    //编写方法删除二叉树的节点(根据值),使删除后仍然使二叉树有序
    public void delete(int delVal){
        //思路分析:
        //因为不能自我删除,需要编写方法找到目标节点的父节点
        //因为要删除的节点可能会有多种不同的情况,要分别分析
        //分3种,1.叶子节点 2.只有一边有子树 3.两边都有子节点
        //先遍历找到target和它的父节点
        Node target = searchNode(delVal);
        Node parent = getParent(delVal);
        //先判断是否找到要删除的节点
        if(target == null){
            System.out.println("删除失败.节点不存在");
            return;
        }
        //如果要删除的节点是根节点
        if(parent == null){
            //让右边的最小值来代替自己
            if(target.right!=null) {
                int i = deleteMin(target.right);
                Node newTarget = new Node(i);
                newTarget.left = target.left;
                newTarget.right = target.right;
            }else {
                //右边为空则左边替代自己
                root = root.left;
            }
            return;
        }
        //如果是叶子节点
        if(target.left==null&&target.right==null){
            if(parent.left == target){
                parent.left = null;
            }else{
                parent.right = null;
            }
            return;
        }
        //如果是有两个子树的节点
        if(target.left!=null && target.right!=null){
            //让右边的最小值来代替target
            int i = deleteMin(target.right);
            Node newTarget = new Node(i);
            if(parent.left == target){
                parent.left = newTarget;
            }else {
                parent.right = newTarget;
            }
            newTarget.left = target.left;
            newTarget.right = target.right;
            return;
        }
        //否则就是只有一颗子树的情况
        if(parent.left == target){
            if(target.left != null){
                parent.left = target.left;
            }else {
                parent.left = target.right;
            }
        }else {
            if(target.left!=null){
                parent.right = target.left;
            }else {
                parent.right = target.right;
            }
        }
    }

    //编写方法,根据传入的节点直接删除该节点
    public void delete(Node target){
        //找到它的父节点
        Node parent = getParent(target);//这个方法不管有无相同值找到的一定就是父节点
        //如果值叶子节点
        if(target.left==null&&target.right==null){
            if(parent.left == target){
                parent.left = null;
            }else{
                parent.right = null;
            }
            return;
        }
        //如果是有两个子树的节点
        if(target.left!=null && target.right!=null){
            //让右边的最小值来代替target
            int i = deleteMin(target.right);
            Node newTarget = new Node(i);
            if(parent.left == target){
                parent.left = newTarget;
            }else {
                parent.right = newTarget;
            }
            newTarget.left = target.left;
            newTarget.right = target.right;
            return;
        }
        //否则就是只有一颗子树的情况
        if(parent.left == target){
            if(target.left != null){
                parent.left = target.left;
            }else {
                parent.left = target.right;
            }
        }else {
            if(target.left!=null){
                parent.right = target.left;
            }else {
                parent.right = target.right;
            }
        }

    }

    //编写方法根据传入的值找到它的父节点返回
    public Node getParent(int val){
        //思路分析,根据大小找
        //如果是根节点,则没有父节点
        if(root == null || root.value == val){
            return null;
        }
        //如果根节点就是父节点
        if(root.right!=null && root.right.value==val || root.left!=null&&root.left.value==val){
            return root;
        }
        //递归查找
        return root.getParent(val);
    }

    //编写方法根据传入的节点找到它的父节点并返回
    public Node getParent(Node node){
        //思路分析,根据大小找
        //如果是根节点,则没有父节点
        if(root == null || root == node){
            return null;
        }
        //如果根节点就是父节点
        if(root.right!=null&&root.right==node || root.left!=null&&root.left==node){
            return root;
        }
        //递归查找
        return root.getParent(node);
    }

    //编写方法找到根据节点找到它的子树的最小值节点删除并返回其值
    public int deleteMin(Node node){
        //不断向左找,最有一定就是最小值节点(二叉排序树的特点)
        Node curNode = node;
        while (curNode.left!=null){
            curNode = curNode.left;
        }
        //根据值删除该节点
        delete(curNode);
        //返回它的值
        return curNode.value;
    }

    //编写方法根据传入的值找到它对应的节点
    public Node searchNode(int val){
        //先判断是否空
        if(root == null){
            return null;
        }
        return root.searchNode(val);
    }

    //编写方法中序遍历二叉树
    public void infixOrder(){
        //先判断是否树空
        if(root == null){
            System.out.println("该排序二叉树空");
            return;
        }
        //中序遍历
        root.infixOrder();
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }
}

/**
 * Node节点类
 */
class Node {
    int value;//值
    Node left;
    Node right;

    //构造器
    public Node(int value) {
        this.value = value;
    }

    //编写方法实现添加节点(平衡二叉树版,需要考虑双旋转的情况)
    public void add(Node node) {
        //思路分析:二叉排序树的节点添加,要保持添加之后有序
        //过程: 让要加入的节点跟自己比较,
        // 如果小于自己,递归加到左边,如果左边为空则直接挂到左边
        // 否则大于自己,递归加到右边,如果右边为空则直接挂到右边
        //先判断是否传入空
        if (node == null) {
            return;
        }
        //判断后添加
        if (node.value < this.value) {
            //如果小于
            if (left == null) {
                left = node;
            } else {
                left.add(node);
            }
        } else {
            //否则大于等于
            if (right == null) {
                right = node;
            } else {
                right.add(node);
            }
        }
        //如果添加完后不平衡,则旋转
        //左旋转
        if(rightHeight()-leftHeight()>1){
            //如果需要双旋转(这个条件发生单纯的左旋转之后仍然不平衡,需要双旋转,将子树先旋转)
            if(right.leftHeight() > right.rightHeight()){
                right.rightRotate();
            }
            leftRotate();
        }
        //右旋转
        if(leftHeight()-rightHeight()>1){
            //如果需要双旋转(这个条件发生,单纯的右旋转也不能使二叉树平衡,需要将子树先旋转)
            if(left.rightHeight()>left.leftHeight()){
                left.leftRotate();
            }
            rightRotate();
        }
    }

    //编写方法递归查找指定值的父节点
    public Node getParent(int val) {
        //根据val的值递归查找
        //先判断自己是不是
        if (right != null && right.value == val || left != null && left.value == val) {
            return this;
        }
        //如果大于,右边找
        if (val > value && right != null) {
            return right.getParent(val);
        }
        //如果小于,左边找
        if (val < value && left != null) {
            return left.getParent(val);
        }
        //如果都没有,说明没找到
        return null;
    }

    //编写方法根据传入的节点查找它的父节点
    public Node getParent(Node node) {
        //根据val的值递归查找,判断是用节点判断
        //先判断自己是不是
        if (right != null && right == node || left != null && left == node) {
            return this;
        }
        //如果大于,右边找
        if (node.value > value && right != null) {
            return right.getParent(node);
        }
        //如果小于,左边找
        if (node.value < value && left != null) {
            return left.getParent(node);
        }
        //如果都没有,说明没找到
        return null;
    }

    //编写方法递归查找指定值的节点
    public Node searchNode(int val) {
        //判断自己是不是
        if (val == value) {
            return this;
        }
        //如果大于
        if (val > value && right != null) {
            return right.searchNode(val);
        }
        //如果小于
        if (val < value && left != null) {
            return left.searchNode(val);
        }
        //如果都没有找到
        return null;
    }

    //编写方法中序遍历二叉树
    public void infixOrder() {
        //中序遍历: 左递归 -----> 自己 -----> 右递归
        //左递归
        if (left != null) {
            left.infixOrder();
        }
        //自己
        System.out.println(this);
        //右递归
        if (right != null) {
            right.infixOrder();
        }
    }

    //编写方法,得到当前节点作为根节点的高度
    public int height(){
         return Math.max(left == null?0:left.height(),right==null?0:right.height())+1;
    }

    //编写方法,返回左子节点的高度
    public int leftHeight(){
        if(left ==null){
            return 0;
        }
        return left.height();
    }

    //编写方法,返回右子树的高度
    public int rightHeight(){
        if(right==null){
            return 0;
        }
        return right.height();
    }

    //编写方法,实现左旋转(降低右子树的高度)
    public void leftRotate(){
        //思路分析:
        //  让自己右边的节点来代替自己,仍然保持二叉树有序点就是左旋转
        // 大概过程: 右边--(代替)-->自己 自己---(跑到)-->左边,
        //创建新的节点保存自己的值
        Node newNode = new Node(value);
        //右边的值覆盖掉自己,右边就代替了自己
        value = right.value;
        //自己(新节点)代替左边
        newNode.left = left;
        newNode.right = right.left;
        left = newNode;
        //原先的right替换根节点去了,就没需要删掉(被垃圾回收机制自动回收)
        right = right.right;
    }

    //编写方法,实现右旋转(降低左子树的高度)
    public void rightRotate(){
        //思路分析:左边替换自己,自己当右边,使二叉树仍然有序
        Node newNode = new Node(value);
        //左边覆盖自己
        value = left.value;
        //自己(新阶段,当右边)
        newNode.left = left.right;
        newNode.right = right;
        right = newNode;
        //删掉原先的左节点
        left = left.left;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
